﻿using System;

namespace _101._对称二叉树
{
    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
        {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public class Solution
    {
        /// <summary>
        /// https://leetcode.cn/problems/symmetric-tree/
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public bool IsSymmetric(TreeNode root)
        {
            return true;
        }

        #region 排序和搜索 https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2322r/
        /// <summary>
        /// https://leetcode.cn/problems/merge-sorted-array/
        /// </summary>
        /// <param name="nums1"></param>
        /// <param name="m"></param>
        /// <param name="nums2"></param>
        /// <param name="n"></param>
        public void Merge(int[] nums1, int m, int[] nums2, int n)
        {
            for (var i = 0; i < n; i++)
            {
                nums1[i + m] = nums2[i];
            }
            Array.Sort(nums1);
        }
        bool IsBadVersion(int version)
        {
            return version >= 662351799;
        }
        /// <summary>
        /// https://leetcode.cn/problems/first-bad-version/solution/
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public int FirstBadVersion(int n)
        {
            //1----n中找一个数据===true
            for (int j = n; j >= 1; j--)
            {
                if (IsBadVersion(j) == false)
                {
                    return j + 1;
                }
            }
            return 1;
        }

        public int FirstBadVersion2(int n)
        {
            //1----n中找一个数据===true int mid = low + (high - low) / 2;

            int low = 1;
            int high = n;

            while (low < high)
            {
                int mid = low + (high - low) / 2;
                if (IsBadVersion(mid)) high = mid;
                else low = mid + 1;
            }
            return high;
        }
        #endregion
    }
    class Program
    {
        static void Main(string[] args)
        {


            //Console.WriteLine(new Solution().FirstBadVersion(5));
            //Console.WriteLine(new Solution().FirstBadVersion2(5));
            //Console.WriteLine(new Solution().FirstBadVersion(1182691386));
            //Console.WriteLine(new Solution().FirstBadVersion2(1182691386));


            //TreeNode tree = new TreeNode(1, new TreeNode(2, new TreeNode(3), new TreeNode(4)), new TreeNode(2, new TreeNode(4), new TreeNode(3)));
            //Console.WriteLine(new Solution().IsSymmetric(tree));
            //Console.WriteLine();
        }
    }
}
